228

Bioinformatics of the Brain

c

d

a

b

e

f

g

FIGURE 9.2

A sample graph to evaluate graph analysis parameters.

Definition 9.2 (degree distribution) The degree distribution of a given

degree k in a graph G is the ratio of the number of vertices with degree k to

the total number of vertices.

We can state degree distribution for a particular degree k of a graph for-

mally as follows.

P(k) = ^nk

n

(9.3)

where nk is the number of vertices with degree k. P(2) = 0.29, P(3) = 0.43,

P(4) = 0.14, and P(5) = 0.14 in the graph of Figure 9.2. Both graph density

and degree distribution give us some idea on the overall global structure of a

graph which may not be adequate for a finer analysis. Formally, the degree

distribution shows the probability of a randomly selected vertex to have a

degree k.

9.3.2

Clustering Coefficient

The clustering coefficient of a node in a graph is another measure of its impor-

tance in the network. A node with highly connected neighbors has a higher

clustering coefficient than a node with sparsely connected neighbors.

Definition 9.3 (clustering coefficient) The clustering coefficient CC(v)

of a node v is the ratio of total number of edges between the neighbors of v to

the maximum number of edges possible between these neighbors.

If a node v has k neighbors, the maximum possible number of connections

among its neighbors is k(k−1)/2. The CC(v) can now be stated as in Eqn. 9.4,

CC(v) =

2x

k(k −1)

(9.4)

where x is the number of edges among neighbors of v. The average clustering

coefficient of a graph G, CC(G), is the arithmetic average of all these values

as CC(G) = ¹

n



v∈V ^{CC(v). The CC values of the vertices in the graph of}

Figure 9.2 are as follows: CC(a) = 1, CC(b) = 0.67, CC(c) = 0.4, CC(d) = 1,

CC(e) = 0.67, CC(f) = 0.67, and CC(g) = 0.5. The characteristic path

length of a network, L, is evaluated by calculating the average value of the

length of all shortest paths between every node pair.